It is assumed that a set of k pieces (k is a natural number) of different binary vectors is called a set of registered vectors. Unique addresses from 1 to k are injected to inputs which coincide with the respective elements of the set of the registered vectors, and a function acting as 0 with respect to the inputs other than the above inputs is called an address generation function. Further, a network for calculating the address generation function is called an address generator. A vector that is applied to the address generator is called an input vector. An address generation function whose input vector is an n-dimensional vector is called an n-input address generation function. Further, a network for calculating the n-input address generation function is called an n-input address generator.
The address generator is also called an associative memory or a content addressable memory (CAM) and used in a wide field of such as pattern matching, a router of the Internet, a cache of a processor, TLB (Translation Lookaside Buffer), data compression, an accelerator of a database, a neural net, a memory path, and the like.
Although it is also possible to realize the function of the address generator using software, the speed of the address generator realized by software is very slow. Accordingly, the address generator is often realized using dedicated hardware (semiconductor memory). A conventional address generator composed of hardware will be explained below.
FIG. 9 is a block diagram showing an example of a basic configuration of a conventional address generator (CAM) (refer to Patent Document 1). The address generator 100 has a comparison register 101, a search bit-line driver 102, k pieces of words W1 to Wk, k pieces of coincidence sensing circuits MSC1 to MSCk, k pieces of coincidence flag registers MFR1 to MFRk, and a priority encoder (coding circuit with priority) PE.
The comparison register 101 is a register for storing n-bit input vectors. The search bit-line driver 102 drives the respective bits of the comparison register 101 on a search bit line. Each of the words W1 to Wk has an n-bit CAM cell.
FIG. 10 is an configuration circuit view of the CAM cell of FIG. 9. The CAM cell 103 exemplified in FIG. 10 is of an incoincidence detection type. The CAM cell 103 is composed of a memory cell 104 and a coincidence comparison circuit 105. The memory cell 104 is a memory cell composed of an SRAM for storing one-bit data. In FIG. 10, D shows data, and DN shows reverse data. The coincidence comparison circuit 105 compares one-bit data stored in the memory cell 104 with an input vector driven on a pair of search bit lines SL, SLN and produces the result of comparison of coincidence on a coincidence line ML.
The coincidence comparison circuit 105 has three nMOS transistors (hereinafter, called “nMOSs”) 106, 107, 108. The nMOSs 106, 107 are connected in series between the search bit lines SLN and SL. The gates of the nMOSs 106, 107 are connected to the data D and the reverse data DN of the memory cell 104, respectively. The nMOS 108 is connected between the coincidence line ML and the ground. The gate of the nMOS 108 is connected to a node 109 between the nMOSs 106, 107.
First, before a search is performed, registered vectors as objects to be searched are stored in the respective words W1 to Wk of the address generator 100. The respective CAM cells 103 in the respective words write data to the memory cell 104 and read out data from the memory cell 104 likewise an ordinary SRAM.
When the search is performed, first, an input vector is stored in the comparison register 101. The respective bits of the input vector are driven on the search bit lines corresponding thereto by the search bit-line driver 102, respectively.
In the respective words W1 to Wk, the coincidence between the registered vectors previously stored in the respective CAM cells 103 and the input vector driven on the search bit line is simultaneously searched (in parallel), and the results are produced on the coincidence lines ML1 to MLk. The results of search of them are applied to the respective coincidence sensing circuits MSC1 to MSCk. The respective coincidence sensing circuits MSC1 to MSCk amplify the results of search and produce them to the coincidence sense output lines MT1 to MTk as coincidence sense produces. The respective coincidence sense outputs are stored in the coincidence flag registers MFR1, to MFRk and produced to coincidence flag output lines MF1 to MFk as coincidence flag produces. It is assumed that the coincidence flag set to ‘1’ shows “coincidence” and the coincidence flag set to ‘0’ shows “incoincidence”.
The respective coincidence flag outputs are applied to a priority encoder PE. The priority encoder PE selects the address of the word having the highest priority order from the words whose coincidence is detected according to a predetermined priority order (highest priority coincidence address: HMA) and produces the address. It is assumed that the priority order of the respective words is such that the word W1 has the highest priority order, and the priority order is sequentially lowered toward the word Wk.
Note that the coincidence search in the respective CAM cells 103 in the respective words W1 to Wk is performed as described below.
First, an initialization operation is performed. In the initialization operation, both the pair of the search bit lines SL, SLN are set to ‘L’(=‘0’). In contrast, one of the nMOSs 106, 107 of the coincidence comparison circuit 105 is placed in an ON state and the other of them is placed in an OFF state according to the data stored in the memory cell 104. Accordingly, the level of the node 109 between both the nMOSs 106, 107 is set to ‘L’ and the nMOS 108 is placed in the OFF state through one of the nMOSs 106, 107 which is placed in the ON state. In the state, the coincidence line ML is precharged to an ‘H’ (=‘1’) state. Note that the coincidence line ML that is set to ‘H’ is shows “coincidence”.
Next, the respective bits of the input vector stored in the comparison register 101 through the search bit line are applied to the respective CAM cells 103. With this operation, any one of the pair of the search bit lines SL, SLN is set to ‘H’ and the other of them is set to ‘L’ according to the input vector S.
When the data D stored in the memory cell 104 coincides with the input vector S, the level of the node 109 is set to ‘L’, and the nMOS 108 is kept in the OFF state.
In contrast, when the data D does not coincide with the input vector S, the level of the node 109 is set to ‘H’, and the nMOS 108 is placed in the ON state. With this operation, the coincidence line ML is discharged and placed in an ‘L’ state.
The coincidence line ML of a CAM word composed of the n-bit CAM cells 103 constitute a wired OR circuit to which the nMOSs 108 of the respective CAM cells 103 are connected in parallel. Accordingly, only when coincidence is detected in all the n-bit CAM cells 103 which constitute one word, the coincidence line ML is held in the ‘H’ (“coincidence”) state. In contrast, when incoincidence is detected in the CAM cells 103 even in one bit, the coincidence line ML is placed in an ‘L’ (“incoincidence”) state.
For example, it is assumed that ‘0’, ‘1’, ‘1’, ‘0’, . . . , ‘1’, and ‘0’ are stored in the coincidence flag registers MFR1 to MFRk as coincidence flags as a result of the search. In this case, the coincidence is detected in the words W2, W3, . . . , Wk−1. Accordingly, the priority encoder PE produces the address of the word W2 having the most priority order as HMA. Further, the address of the word W3 having the next highest priority order can be produced as HMA by clearing the coincidence flag stored in the coincidence flag register MFR2 to ‘0’, Hereinafter, the addresses of the words whose coincidence is detected can be sequentially produced likewise.
FIG. 11 is a circuit diagram of an configuration of other example of the CAM cell of FIG. 9. A CAM cell 103′ shown in FIG. 11 is of a coincidence detection type and has a memory cell 104 composed of an SRAM and a coincidence comparison circuit 105 likewise FIG. 10. The CAM cell 103′ is different from the CAM cell 103 of FIG. 10 in that the coincidence comparison circuit 105 is connected to an nMOS 108 in a different manner. The nMOS 108 of FIG. 11 is connected between a coincidence line MLa and a coincidence line MLb. The gate of the nMOS 108 is connected to a node 109 between nMOS transistors 106, 107.
In the CAM cell 103′, when a search is performed, both a pair of bit lines SL, SLN are set to ‘H’ as an initialization operation. In contrast, one of the nMOSs 106, 107 of the coincidence comparison circuit 105 is placed in the ON state and the other of them is placed in the OFF state according to the data stored in the memory cell 104. Accordingly, the level of the node 109 between both the nMOSs 106, 107 is set to ‘H’ and the nMOS 108 is placed in the ON state through one of the nMOSs 106, 107 which is in the ON state. In this state, one end of the coincidence line ML is precharged to the ‘H’(=‘1’) state. Note that the coincidence line ML that is set to ‘H’ shows “incoincidence”.
The coincidence line ML of CAM words composed of the n-bit CAM cells 103 constitute an AND circuit to which the nMOSs 108 of the respective CAM cells 103′ are serially connected. Accordingly, the coincidence lines MLa, MLb of the respective CAM cells are precharged to ‘H’ through the nMOSs 108 of the respective CAM cells 103′.
Thereafter, the respective bits of the input vector stored in a comparison register 101 are applied to the respective CAM cells 103′ through a search bit line. With this operation, any one of the pair of the search bit lines SL, SLN is set to ‘H’ and the other of them is set to ‘L’ according to the input vector S.
When the data D stored in the memory cell 104 coincides with the input vector S, the level of the node 109 is ‘H’, and the nMOS 108 is held in the ON state.
Whereas, when the data D does not coincide with the input vector S, the level of the node 109 is set to ‘L’, and the nMOS 108 is placed in the OFF state.
After all the states of the n-bit CAM cells 103′ of the CAM words are fixed, a discharge is started from one end of the coincidence line ML, and a result of comparison of coincidence is determined by the other end thereof. At the time, when there is an incoincident CAM cell 103′ even in one bit, the result of coincidence of comparison is ‘H’, that is, the result is held in the state of incoincidence. In contrast, only when incoincidence is detected in all the CAM cells 103′, the result of comparison of coincidence is set to ‘L’, that is, it is placed in a coincidence state.    [Patent Document 1]    Japanese Unexamined Patent Application Publication No. 2004-295967    [Patent Document 2]    Patent Application No. 2003-389264    [Patent Document 3]    Japanese Unexamined Patent Application Publication No. 2004-258799    [Patent Document 4]    U.S. Pat. No. 5,063,573    [Non-Patent Document 1]
“Ultra high speed device series 2 Ultra high speed MOS device”, supervised by Tadao Kanno, edited by Susumu Koyama, first edition, Baihukan, February 1986, pp. 324-325.    [Non-Patent Document 2]
“LSI hand book”, edited by The Institute of Electronics, Information and Communication Engineers, first edition, Ohm Sha, November 1994, pp 523-525.    [Non-Patent Document 3]
Kostas Pagiamtzis and Ali Sheikholeslami, “A Low-Power Content-Addressable Memory (CAM) Using Pipelined Hierarchical Search Scheme”, IEEE Journal of Solid-State Circuits, Vol. 39. No. 9, September 2004, pp. 1512-1519.    [Non-Patent Document 4]
T. Sasao, M. Matsuura, and Y. Iguchi, “A cascade realization of multi-output function for reconfigurable hardware”, International Workshop on Logic and Synthesis (IWLSO1), Lake Tahoe, Calif., Jun. 12-15, 2001, pp. 225-230.    [Non-Patent Document 5]
T. Sasao and M. Matsuura, “BDD representation for incompletely specified multiple-output logic functions and its applications to functional decomposition”, Design Automation Conference, June 2005, (pp. 373-378).